package com.jia.explore.dynamicprogramming.knapsack;

import java.util.Scanner;

/**
 * @program: Leetcode
 * @description: 多重背包 https://www.acwing.com/problem/content/4/
 * @author: STU756
 * @create: 2020-08-11 12:50
 */
public class Dy_MatrixBackpack {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int v = scanner.nextInt();
        int m = scanner.nextInt();
        int N = 110;
        int[][] dp = new int[N][N]; //f[i][j] 前i个物体重量小于等于j最大价值
        for (int i = 1; i <= n; i++) {
            int vi = scanner.nextInt();
            int mi = scanner.nextInt();
            int wi = scanner.nextInt();
            for (int j = v; j >= vi; j--) {
                for (int k = m; k >= mi; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - vi][k - mi] + wi);
                }
            }
        }
        System.out.println(dp[v][m]);
    }

}
